package org.example.BitVetory;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

// 位向量存储数据
public class BitVector {
    private final int count;
    private final int[] a;  // 数组
    private final int BIT_LENGTH = 32;  // 默认使用int类型
    private final int MASK = 0x1F;  // 2^5 - 1
    private final int SHIFT = 5;    // 2^n SHIFT=n=5 表示2^5=32 即bit位长度32

    // 初始化位向量, count为无序数的数量
    public BitVector(int count) {
        this.count = count;
        a = new int[(count - 1) / BIT_LENGTH + 1];
        init();
    }

    // 将数组中元素bit位设置为0
    public void init() {
        for (int i = 0; i < count; i++) {
            clear(i);
        }
    }

    // 置位操作,设置元素; i表示第几个元素(1开始)
    public void set(int i) {
        a[i >> SHIFT] |= (1 << (i & MASK));
    }

    // 置0操作，相当于清除元素; i表示第几个元素(1开始)
    public void clear(int i) {
        a[i >> SHIFT] &= ~(1 << (i & MASK));
    }

    // 读取操作，返回 1 代表该bit位有值，返回 0 代表该bit位没值
    // i表示第几个元素(1开始)
    public int get(int i) {
        return Integer.bitCount(a[i >> SHIFT] & (1 << (i & MASK)));
    }

    // 获取排序后的数组
    public List<Integer> getSortedArray() {
        List<Integer> sortedArray = new ArrayList<>();
        for (int i = 0; i < count; i++) {
            if (get(i) == 1) {  // 判断i是否存在
                sortedArray.add(i);
            }
        }
        return sortedArray;
    }

    // 获取测试用例，一组随机无序整数的List集合
    private static List<Integer> getRandomsList(int count) {
        Random random = new Random();
        List<Integer> randomsList = new ArrayList<>();
        while (randomsList.size() < (count - 1) / 2) {
            int element = random.nextInt(count - 1) + 1;    // element ∈ [1,count)
            if (!randomsList.contains(element)) {
                randomsList.add(element);
            }
        }
        return randomsList;
    }

    public static void main(String[] args) {
        int count = 25;
        List<Integer> randoms = getRandomsList(count);

        System.out.println("排序前：");
        BitVector bitVector = new BitVector(count);
        for (Integer e : randoms) {
            System.out.print(e + ",");
            bitVector.set(e);
        }
        System.out.println();

        List<Integer> sortedArray = bitVector.getSortedArray();
        System.out.println("排序后：");
        for (Integer e : sortedArray) {
            System.out.print(e + ",");
        }

        /* 输出结果:
         排序前：
         6,3,20,10,18,15,19,16,13,4,21,22,24,2,14,5,12,7,23,8,1,17,9,11,
         排序后：
         1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,
         */
    }
}

